import java.util.Arrays;

/**
 * https://leetcode.cn/problems/relative-sort-array/description/
 * 视频：https://www.bilibili.com/video/BV1rv4y1H7o6?spm_id_from=333.788.videopod.episodes&vd_source=36dbb0f6eb577254888df3bf9b4ce456&p=67
 * @author liuzhaoqiang
 */
public class LeetCode1122 {
    /**
     * 1 <= arr1.length, arr2.length <= 1000
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //记录 arr1 中数字出现的次数 角标就是 arr1 的元素值，值就是次数
        int[] count = new int[1001];
        for (int i : arr1) {
            count[i]++;
        }
        int[] result = new int[arr1.length];
        int k=0;
        for (int i : arr2) {
            while(count[i]>0){
                count[i]--;
                result[k++] = i;
            }
        }
        //剩下的 7，,19还没有排序
        for (int i = 0; i < count.length; i++){
            while(count[i]>0){
                result[k++] = i;
                count[i]--;
            }
        }
        System.out.println(Arrays.toString(count));
        return result;
    }

    public static void main(String[] args) {
        LeetCode1122 leetCode1122 = new LeetCode1122();
        int[] ints = leetCode1122.relativeSortArray(new int[]{2,3,1,3,2,4,6,7,9,2,19}, new int[]{2,1,4,3,9,6});
        System.out.println(Arrays.toString(ints));
    }
}
